#include <stdio.h>
#include "mybintree.h"
/*建立一个二叉树*/
BINNODE *createbt(){
    BINNODE *q;//临时生成的新结点 
    BINNODE *s[30];//指针数组，存放二叉树中的所有结点，最多只能有30个结点 
    int j,i;
    datatype x;//结点的数据域的值 
    printf("建立二叉树，输入结点对应的编号和值，编号和值之间用逗号隔开，编号从1开始，值以'$'为结束\n");
    printf("编号,字母=");
    scanf("%d,%c",&i,&x);
    while(i!=0&&x!='$'){
        q=(BINNODE *)malloc(sizeof(BINNODE));/*建立新结点*/
        q->data=x;/*x放入数据域*/
        q->lchild=NULL;
        q->rchild=NULL;/*左右孩子都为空*/
        s[i]=q;/*q结点地址存入s指针数组中*/
        if(i!=1){/*i=1，对应的结点是根结点*/
            j=i/2;/*求双亲结点的编号j*/
            if(i%2==0){
                s[j]->lchild=q;/*q结点编号为偶数则挂在双亲结点j的左边*/
			}else{
                s[j]->rchild=q;/*q结点编号为偶数则挂在双亲结点j的右边*/
			}
		}
		printf("编号,字母=");
		scanf("%d,%c",&i,&x);
	}
	return s[1];//返回根结点地址
}
/*先序遍历二叉树，递归实现*/
void preorder(BINNODE *root){
    if(root!=NULL){
    	printf("%c",root->data);/*访问根结点*/
    	preorder(root->lchild);/*访问左子树*/
    	preorder(root->rchild);/*访问右子树*/
	}
}
/*中序遍历二叉树，递归实现*/
void inorder(BINNODE *root){
    if(root!=NULL){
    	inorder(root->lchild);/*访问左子树*/
		printf("%c",root->data);/*访问根结点*/
    	inorder(root->rchild);/*访问右子树*/
    }
}
/*后序遍历二叉树，递归实现*/
void postorder(BINNODE *root){
    if(root!=NULL){
    	postorder(root->lchild);/*访问左子树*/
    	postorder(root->rchild);/*访问右子树*/
    	printf("%c",root->data);/*访问根结点*/
    }
}

/*求叶子结点数*/
int numOfLeaf(BINNODE *root)
{
    if(root==NULL)
        return 0;
    else if(root->lchild==NULL && root->rchild==NULL) 
        return 1;
    else
        return numOfLeaf(root->lchild)+numOfLeaf(root->rchild);
} 
